/*
    Aufgabe 2) Zweidimensionale Arrays und Rekursion - Sudoku
*/

public class Aufgabe2 {
    
    private static final int sSize = 9; //sudoku field size ==> 9x9
    private static final int subSize = 3; //sudoku subfield size ==> 3x3

    private static int[][] readArrayFromFile(String filename) {
        // init
        In reader = new In(filename);
        int[][] playfield = new int[sSize][sSize];
        String[] splitLine;

        // parsing
        for (int i = 0; i < sSize && reader.hasNextLine(); i++) {
            // split line into individual cells
            splitLine = reader.readLine().split(";");

            // iterate cells
            for (int j = 0; j < sSize; j++) {
                // parse cell
                playfield[i][j] = Integer.parseInt(splitLine[j]);
            }
        }

        return playfield;
    }
    
    private static boolean solveSudoku(int[][] array, int idx) {
        if (idx > (sSize * sSize - 1)) {
            return true;
        } else {
            if (array[idx / sSize][idx % sSize] == 0) {
                for (int num = 1; num <= sSize; num++) {
                    if (!isNumUsedInRow(array, num, idx / sSize) && !isNumUsedInCol(array, num, idx % sSize) && !isNumUsedInBox(array, num, idx / sSize - ((idx / sSize) % subSize), idx % sSize - ((idx % sSize) % subSize))) {
                        array[idx / sSize][idx % sSize] = num;
                        if (solveSudoku(array, idx + 1)) {
                            return true;
                        } else {
                            array[idx / sSize][idx % sSize] = 0;
                        }
                    }
                }
            } else {
                return solveSudoku(array, idx + 1);
            }
        }
        return false;
    }
    
    private static boolean isNumUsedInBox(int[][] array, int num, int row, int col) {
        if (row % subSize != 0 || col % subSize != 0) {
            System.out.println("isnumusedinbox: invalid values supplied for row, col");
            return false;
        }

        for (int i = row; i < row + subSize; i++) {
            for (int j = col; j < col + subSize; j++) {
                if (array[i][j] == num) return true;
            }
        }

        return false;
    }
    
    private static boolean isNumUsedInRow(int[][] array, int num, int row) {
        for (int i = 0; i < sSize; i++) {
            if (array[row][i] == num) return true;
        }

        return false;
    }
    
    private static boolean isNumUsedInCol(int[][] array, int num, int col) {
        for (int i = 0; i < sSize; i++) {
            if (array[i][col] == num) return true;
        }

        return false;
    }
    
    private static boolean isValidSudokuSolution(int[][] array) {
        for (int num = 1; num <= sSize; num++) {
            // loop boxes
            for (int row = 0; row < sSize; row += subSize) {
                for (int col = 0; col < sSize; col += subSize) {
                    if (!isNumUsedInBox(array, num, row, col))
                        return false;
                }
            }

            // loop rows and cols
            for (int i = 0; i < sSize; i++) {
                if (!isNumUsedInRow(array, num, i))
                    return false;
                if (!isNumUsedInCol(array, num, i))
                    return false;
            }
        }

        return true;
    }
    
    private static void printArray(int[][] inputArray) {
        for (int y = 0; y < inputArray.length; y++) {
            for (int x = 0; x < inputArray[y].length; x++) {
                System.out.print(inputArray[y][x] + "\t");
            }
            System.out.println();
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        
        String filename;
        int[][] sudokuField = null;

        for (int fileIndex = 0; fileIndex <= 7; fileIndex++) {
            filename = "sudoku" + fileIndex + ".csv";
            System.out.println("Reading " + filename + " ...");
            sudokuField = readArrayFromFile(filename);
            printArray(sudokuField);
            solveSudoku(sudokuField, 0);

            System.out.println("sudoku solved");
            System.out.println("valid solution: " + isValidSudokuSolution(sudokuField));
            printArray(sudokuField);
            System.out.println();
        }
    }
}


